package searchandsort;

public class FindMinimumInRotatedSortedArray153 {
    public int findMin(int[] nums) {
        return findMin(0, nums.length - 1, nums);
    }

    private int findMin(int begin, int end, int[] nums) {
        if (begin > end) {
            return -1;
        }
        if (begin == end) {
            return nums[begin];
        }
        if (begin + 1 == end) {
            return nums[begin] < nums[end] ? nums[begin] : nums[end];
        }

        int mid = (begin + end) / 2;
        if (nums[mid] <= nums[(mid + 1) % nums.length] &&
                nums[mid] <= nums[(mid + nums.length - 1) % nums.length]) {
            return nums[mid];
        }
        if (nums[mid] > nums[begin]) {
            if (nums[begin] > nums[end]) {
                return findMin(mid + 1, end, nums);
            } else {
                return findMin(begin, mid - 1, nums);
            }
        }

        if (nums[mid] < nums[end]) {
            if (nums[begin] > nums[end]) {
                return findMin(begin, mid - 1, nums);

            } else {
                return findMin(mid + 1, end, nums);

            }
        }
        return -1;
    }
}
